20220225-TIL

‘BaaarkingDog’ 님 강의 영상을 보고 공부했다. (플로이드 알고리즘.. 응용문제는 엄청 어렵겠지..?)

• 그래프상의 모든 정점을 연결하는 최단 경로/거리를 구하는 플로이드 알고리즘에 대해서 배웠다.
• 최단 경로를 구성하는 부분 경로를 기록해두면, 최단 경로 전체를 복원할 수 있다는 것을 배웠다.
• 플로이드 알고리즘의 시간 복잡도는, 정점의 개수가 v개일 때, O(v^3) 이 된다는 것을 알게 됐다.
  (정점이 1,000개 이하라면 사용 가능 -> 불필요한 대입 연산을 줄이는 방법 사용(상수 시간 최적화))
• 연습문제(최단 거리만 구하는 문제, 경로까지 복원하는 문제) 도 풀어봤다. (금방 익숙해질 듯?!)